// 括号。设计一种算法，打印n对括号的所有合法的（例如，开闭一一对应）组合。
// 说明：解集不能包含重复的子集。

// 暴露接口
const generateParenthesis = function (n: number): string[] {
    const res: string[] = []; // 结果数组\
    return generateParenthesis_DFS(res, '', n, n)
};
// 深度优先遍历辅助方法
function generateParenthesis_DFS(res: string[], currStr: string, left: number, right: number): string[] {
    if (left === 0 && right === 0) { // 递归终点
        res.push(currStr);
        return res;
    }
    // 优先匹配左括号
    if (left > 0) {
        generateParenthesis_DFS(res, currStr + "(", left - 1, right)
    }
    //剪枝，注意什么是有效的括号
    if (right > left) {
        generateParenthesis_DFS(res, currStr + ")", left, right - 1)
    }
    return res;
}


generateParenthesis(2)

// 这道题注意一下当前递归轮次中哪些状态是要保存的，哪些是保存在下个轮次的要注意
// 不然会出现结果的重复。